 package com.atguigu.sort;

 import java.util.Arrays;

 /**
 * @author shengxiao
 * @date 2021/7/19 16:55
  * 注意：希尔排序分的组越多，每个组的元素个数就越少
  *
  * 希尔排序法介绍
  *
  * 希尔排序是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序。
  *
  * 希尔排序法基本思想
  *
  * 希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止
  *
  *
 */
public class ShellSort {

    public static void main(String[] args) {
//        int[] arr = {8,9,1,7,2,3,5,4,6,0} ;
//        shellSort2(arr);

        // 创建80000个的随机的数组
        int[] arr = new int[8000000] ;
        for(int i = 0 ; i < 8000000 ; i++){
            arr[i] = (int) (Math.random() * 800000000);  // 生成一个[0,8000000)的数，为什么要取怎么大，为了避免取到相同的值
        }
//        Date date1 = new Date() ;   // 实体类
//        SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
//        String date1Str = sdf.format(date1);
//        System.out.println("排序前的时间是=" + date1Str);

        long before = System.currentTimeMillis() ;
        //System.out.println("排序前的时间是=" + System.currentTimeMillis()) ;

        //shellSort(arr);
        shellSort2(arr);

//        Date date2 = new Date() ;   // 实体类
//        String date2Str = sdf.format(date2);
//        System.out.println("排序后的时间是=" + date2Str);  // 选择排序用时4s
        long after = System.currentTimeMillis() ;
        //System.out.println("排序后的时间是=" + System.currentTimeMillis()) ;
        System.out.println("执行总时间" + (after - before) / 1000.0 + "s");  // 对交换式的希尔排序:执行总时间8.246s,速度太慢了
                                                                           //  对移位式的希尔排序：80000条数据执行总时间0.02s
                                                                           //                  800000条数据执行总时间0.304s，说明还是快排要快
                                                                           //                  8000000条数据执行总时间2.654s,比快排要慢

    }

    // 使用逐步推导的方式来编写希尔排序
    // 希尔排序时，对有序序列在插入时采用交换法，会存在类似组内冒泡排序【一看到一个顺序不符合就交换顺序；】，
    // 但实际上这个算法终究还是以插入排序为基本的而不是冒泡排序，不过这里的写法和前面的直接插入排序的写法有些不同，冗余度更大
    // 而交换法的插入排序故最后排序的速度会比较慢，说明可能存在大量的无效的交换判断。
    // 思路（算法）===》代码
    // 注意：分组数和步长是相同的，即如果分为5组，则步长为5，但是【分组，步长】和 能遍历的次数是没有关系的

     /**
      * 交换法：如果发现两个数存在前面大于后面的情况下，立刻交换【类似冒泡】
      *  *****注意：
      *     其实我理解错误了，并不是"类似冒泡"，而是类似插入排序，
      *     只是此时我们是将要插入的元素参与了交换顺序，而交换的过程中好像是在进行插入排序的一趟遍历搜索。
      * 其实gap既可以当做分组数【增量数】，有说明了每个元素之间的间隔数
      */
    public static void shellSort(int[] arr){

        int temp = 0 ;  // 减少内存空间开辟的消耗，故定义在for循环外，只声明一次
        int count = 0 ; // 计数器，经过几趟的排序
        // 根据前面的逐步分析，使用循环处理
        // gap：分组数，即增量数，要逐渐减少，到最后的1为止
        for(int gap = arr.length / 2 ; gap > 0 ; gap /= 2){ // 每趟分组排序都需要进行gap/=2,第一趟排序需要对gap=arr.length/2
            // 为什么要这样定义i = gap？因为第x轮排序分成了gap组，故初始值要从i=gap开始计数，此循环遍历(arr.length-gap)次，而且后面arr.length长度是需要进行处理的
            // 而且，切记：下面这个for循环对于某个分组的交换排序并不是一步到位的，
            // 假设原来有100个元素，那么第一趟分组，分为100/2=50组【每个元素间隔位移是50，此时刚好可以一步遍历就可以比较完成，因为每组只有两个元素】
            // 而第二趟分组，分为50/2=25组，每组为100/25=4个数组【每个元素间隔位移是25，每组 共有4个元素，但此时每组的四个元素，并不能一次性比较交换完成，注：一次只能比较交换两个元素】
            // 需要从gap出发，直到arr.length-1 ，即【gap,arr.length-1】都遍历一遍，那么如果是第一组而言，元素所处位置是0，25,50,75，
            // 当i到达指定的索引位置时候，刚好对之前间隔gap排好序的元素，加上这次要排序要再进行简单插入排序，【相当于前面的排好的元素作为有序表】，接下来要插入的元素作为无序表
            // 此时依次将要插入的元素和有序表的最后一个元素进行比较【交换式希尔排序】，按照类似简单插入排序规则，进行排序。
            for(int i = gap ; i < arr.length ; i++){
                // 即为下面的for循环服务，下面要分为5组，故存在下标为0和5,1和6,2和7。。。5组【步长为5，每组进行简单插入排序】
                // 5组为[8,3]   [9，5]     [1,4]     [7,2]     [2,0]   跨度为5，即步长为5

                // 遍历各组中所有的元素（共有gap组，每组有XX个元素，），步长为gap
                // 注意：为什么初始化时j要减gap，因为要遍历每一组，而第一组的第一个元素是在j=i-gap处，

                for(int  j = i - gap; j >= 0 ; j -= gap){   // 此处的j代表步长，j -= gap -》 步长减gap
                    // 如果当前元素大于加上步长后的那个元素 ，说明交换
                    if(arr[j] > arr[j + gap]){
                        temp = arr[j] ;
                        arr[j] = arr[j + gap] ;
                        arr[j + gap] = temp ;
                    }
                }
            }
            //System.out.println("希尔排序第" + (++count) + "轮=" + Arrays.toString(arr));
        }
/*
        int temp = 0 ;  // 减少内存空间开辟的消耗，故定义在for循环外，只声明一次
        // 希尔排序的第一轮排序
        // 因为第一轮排序，是将10个数据分成了 10/2=5组, 1组有2个数据
        for(int i = 5 ; i < arr.length ; i++){  // 为什么要这样定义i = 5？因为第一轮排序分成了5组，所以此循环遍历(arr.length-5)次，而且后面arr.length长度是需要进行处理的
            // 即为下面的for循环服务，下面要分为5组，故存在下标为0和5,1和6,2和7。。。5组【步长为5，每组进行简单插入排序】
            // 5组为[8,3]   [9，5]     [1,4]     [7,2]     [2,0]   跨度为5，即步长为5

            // 遍历各组中所有的元素（共有5组，每组有2个元素，），步长5
            // 注意：为什么初始化时j要减5，因为要遍历每一组，而第一组的第一个元素是在j=i-5处，
            for(int j = i - 5 ; j >= 0 ; j -= 5){   // 此处的j代表步长，j -= 5 -》 步长减5
                // 如果当前元素大于加上步长后的那个元素 ，说明交换
                if(arr[j] > arr[j + 5]){
                    temp = arr[j] ;
                    arr[j] = arr[j + 5] ;
                    arr[j + 5] = temp ;
                }
            }
        }

        System.out.println("希尔排序第1轮后=" + Arrays.toString(arr));
        // 希尔排序第1轮后=[3, 5, 1, 6, 0, 8, 9, 4, 7, 2]

        // 希尔排序的第2轮排序
        // 因为第2轮排序，是将10个数据分成了5/2=2组
        for(int i = 2 ; i < arr.length ; i++){  // 为什么要这样定义i=2？因为第二轮排序分成了2组，所以此循环遍历(arr.length-2)次，而且后面arr.length长度是需要进行处理的
            // 即为下面的for循环服务，下面要分为2组，故存在下标为0,2,4,6,8 和1 3 5 7 9【步长为2，每组进行简单插入排序】
            // 2组为[3,1,0,9,7]   [5,6,8,4,2]   跨度为2，即步长为2

            // 遍历各组中所有的元素（共有5组，每组有2个元素，），步长2

            for(int j = i - 2 ; j >= 0 ; j -= 2){   // 此处的j代表步长，j -= 2 -》 步长减2
                // 如果当前元素大于加上步长后的那个元素 ，说明交换
                if(arr[j] > arr[j + 2]){
                    temp = arr[j] ;
                    arr[j] = arr[j + 2] ;
                    arr[j + 2] = temp ;
                }
            }
        }
        System.out.println("希尔排序第2轮后=" + Arrays.toString(arr));
        // 希尔排序第2轮后=[0, 2, 1, 4, 3, 5, 7, 6, 9, 8]

        // 希尔排序的第3轮排序
        // 因为第3轮排序，是将10个数据分成了2/2=1组
        for(int i = 1 ; i < arr.length ; i++){  // 为什么要这样定义i=1？因为第三轮排序分成了1组，所以此循环遍历(arr.length-1)次，且符合前面arr.length-1个位置排列好了，最后一个位置就不用排了
            // 即为下面的for循环服务，下面要分为1组，故存在下标为0,1,2,3,4,5,6,7,8,9 【步长为1，每组进行简单插入排序】
            // 1组为[0, 2, 1, 4, 3, 5, 7, 6, 9, 8]  跨度为1，即步长为1

            // 遍历各组中所有的元素（共有5组，每组有2个元素，），步长1

            for(int j = i - 1 ; j >= 0 ; j -= 1){   // 此处的j代表步长，j -= 1 -》 步长减1
                // 如果当前元素大于加上步长后的那个元素 ，说明交换
                if(arr[j] > arr[j + 1]){
                    temp = arr[j] ;
                    arr[j] = arr[j + 1] ;
                    arr[j + 1] = temp ;
                }
            }
        }
        System.out.println("希尔排序第3轮后=" + Arrays.toString(arr));*/
    }

     // 对交换式的希尔排序进行优化-》移位法

     /**
      * 移动法：按照之前直接插入法中，移动位置的方式来处理，即对于用gap分组的每一组而言，如果前面大于后面的情况下，不马上交换，先后移，
      *        直到找到temp该去的位置，然后一次性进行交换，此法的速度会明显提升【和直接插入方法类似，区别在于直接插入法的insertIndex初始值是位于有序表的最后一个位置，
      *        而此处位移式的希尔排序，对于用gap分组的每一组，都利用到了直接排序法，但此处的temp设置为gap分组的下标位置，然后和】
      *
      *        // 假设原来有100个元素，那么第一趟分组，分为100/2=50组【每个元素间隔位移是50，此时刚好可以一步遍历就可以比较完成，因为每组只有两个元素】
      *        // 而第二趟分组，分为50/2=25组，每组为100/25=4个数组【每个元素间隔位移是25，每组 共有4个元素，但此时每组的四个元素，并不能一次性比较完成，注：一次只能比较两个元素】
      *        // 需要从gap出发，直到arr.length-1 ，即【gap,arr.length-1】都遍历一遍，那么如果是第一组而言，元素所处位置是0，25,50,75，
      *        // 当i到达指定的索引位置时候，刚好对之前间隔gap排好序的元素，加上这次要排序要再进行简单插入排序，【相当于前面的排好的元素作为有序表】，接下来要插入的元素作为无序表
      *        // 此时依次将要插入的元素和有序表的最后一个元素进行比较，按照简单插入排序规则，如果要插入的元素比当前有序表的最后一个元素还要小，则先移动有序表的位置，直到
      *        // 要么下标越界，退出循环，或者找到了一个要插入的元素比待插入位置要大的元素，此时就移动完毕，然后直接将待插入的元素填充在指定位置。【好处：减少了交换移动的次数】
      *
      * 综上：其实移动法可以形象的看做是在gap步长的简单插入排序。其实我们也可以假设下面的temp=arr[j]前面的元素对应的每一组的数据都是有序列表，此时相当于后面的每一组的无序列表要依次进行排列
      *     这里的希尔排序的移动法其实是直接插入排序的特殊版，直接插入排序是和前面已经排列完的数据进行比较，
      *     而希尔排序的移动法是在每一次增量下要插入的元素和【前面有序的数据，假设第一趟排序已经将一部分数据小的元素往前挪，那个在每个分组下，对应的每一个分组的第一个元素都是有序表】进行比较。二者大同小异
      * @param arr
      */
     public static void shellSort2(int[] arr){

        // 增量gap，并逐步的缩小容量
        for(int gap = arr.length / 2 ; gap > 0 ; gap /= 2){
            // 从第gap个元素，逐个对其所在的组进行直接插入排序
            for(int i = gap ; i < arr.length ; i++){    // 遍历arr.lengh-gap次数，刚开始是从gap个分组的第一个分组的数据arr[j]中和前一个gap位置的arr[j-gap]进行比较，查看是否有无比arr[j]还要大的元素
                int j = i ;     // j：待插入的元素的下标，这并不是 要插入到有序列表具体位置的索引值（下标） ；这和直接插入排序中的insertIndex不同，那里的insertIndex是有序表的最后一个元素
                // 将待插入【即交换】位置的下标保存下来到j，和直接排序不同点在于，
                // 直接排序待插入【即交换】位置的初始值为有序表的最后一个位置，而这里待插入的位置就是涵盖了交换的步骤，故不用设置为前一个
                int temp = arr[j] ;   // 将待插入的值保存到temp
                // 注意：有人说，这里的if语句和下面的while循环的一个判断条件重复了，其实并没有重复
                // 解释1：因为分组之后有部分组是有序的，你如果不进行判断就要全部比较一遍。
                // 解释2: if不重复，因为是从前往后，所以每一次前面都是有序的，这样如果大于有序表的最后一个元素就不用排了，所以加if是改进
                // 解释3：if是对while的优化，如果待插入数据已经在正确的位置就不用找了
                // 解释4：if条件是对第一次 多组数据优化，因为每组只有两个；while里面用在最后一趟的一组gap=1，，因为要比较全部数据【注意：无论要排列多少个元素，第一趟排序无论分为几组，每组的数据都是2个，因为arr.length/2=gap】
                // 解释5：if是减少进入while的次数
                // 综上：还是加上吧，反正加与不加对处理的速度差别不大
                if(arr[j] < arr[j - gap]){  // 说明后面的值比前面的要小，极端点考虑：arr[j]至少当前是第二个元素，第一个arr[j-gap]是当前组的第一个元素，是不是恰好也是有序列表，刚好符合
                    //注意：假设i初始值为gap，这里为什么要写成j-gap？因为要让当前处于gap位置[即j的取值]的元素和0的位置元素进行比较
                    // j - gap >= 0：说明还可以继续找位置，如果j - gap < 0 ,则temp找到了插入的位置
                    // temp < arr[j - gap]：说明待插入元素temp比索引-gap位置的arr[j - gap]值要小
                    // 其实我们可以形象的看一下，对于上面的int i = gap，int j = i;的情况，这里temp就相当于和当前组的第一个元素j-gap进行比较，也就是和有序表的最后一个元素进行比较
                    // 极端点考虑：arr[j]至少当前是第二个元素，第一个arr[j-gap]是当前组的第一个元素，是不是恰好也是有序列表，刚好符合
                    while(j - gap >= 0 && temp < arr[j - gap]){
                        // 移动
                        // 切记：如果存在多次移动，说明在tap分组下的，某一个分组此时要插入的元素的前面的元素已经是有序列表，则后面的元素 依次进行判断，利用直接插入排序的思想
                        arr[j] = arr[j - gap] ; // 此时需要将前一个步长的元素移动到当前元素处
                        j -= gap ;  // 将要插入位置的下标减去一个gap【步长】
                    }

                    // 当退出while循环后，就给temp找到插入的位置
                    // 因为满足while循环时，在移动元素时候，最后存在移动指示器j的位置，即j-gap；如果刚好移动一次就可以跳出循环
                    // 但是因为j-gap，故此时不是指向插入位置，而是其前一个位置；故这里如果要插入元素，则需要j-gap+gap
                    // 而这里为什么和直接插入排序优点区别的地方，那就是之前定义要插入指定位置的j，
                    // 希尔排序：此处的j=i，故在最后退出while时候，arr[j - gap + gap] ，j-gap表示待插入到指定位置的下标，后面+gap，是在不满足条件时候，j又多减去了一次gap
                    // 故最后为arr[j - gap + gap] = temp;   但是 我们何必多次一举呢？这里的j就是待插入元素的下标，即最后arr[j] = temp ;
                    // 而直接插入排序则为j = insertIndex =  i - 1；insertIndex表示待插入到指定位置的下标，在不满足条件时候，j = insertIndex 又多减去了一次1
                    // 故最后若要实现指定位置的插入，insertIndex+1，此时刚好可以插入。也就是arr[insertIndex + 1] = insertVal ;
                    // 综上：这两个思想大致相同，都是先找到要插入的位置，再进行交换。区别就在于变量定义的方式不同，导致最后的写法不同。
                    //      如果我也想和直接插入的写法一致，那也可以；思路是一样的。
                    arr[j] = temp ;


                    //arr[j - gap + gap] = temp ; // 将前面保存了arr[j]副本的temp变量赋值给
                }

            }
            //System.out.println(Arrays.toString(arr));
        }
     }
}
